import java.util.Stack;

/**
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 * <p>
 * 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [1,3,null,null,2]
 * 输出：[3,1,null,null,2]
 * 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [3,1,4,null,null,2]
 * 输出：[2,1,4,null,null,3]
 * 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 *  
 * <p>
 * 提示：
 * <p>
 * 树上节点的数目在范围 [2, 1000] 内
 * -231 <= Node.val <= 231 - 1
 */
class Solution {

    public static void main(String[] args) {
     /*   TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.right = node2;
        node2.left = node3;
        recoverTree(node1);
        System.out.println(node1);*/

        /*TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left = node3;
        node3.right = node2;
        recoverTree(node1);
        System.out.println(node1);*/

        /*TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node2 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        node1.left = node3;
        node3.left = node2;
        node2.left = node4;
        recoverTree(node1);
        System.out.println(node1);*/

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node2.left = node3;
        node2.right = node1;
        recoverTree(node2);
        System.out.println(node2);

        /*TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node2.right = node1;
        node1.right = node3;
        recoverTree(node2);
        System.out.println(node2);*/

        /*TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node2.left = node1;
        node1.right = node3;
        recoverTree(node2);
        System.out.println(node2);*/

        /*TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node3.right = node1;
        node1.left = node2;
        recoverTree(node3);
        System.out.println(node3);*/

        /*TreeNode node3 = new TreeNode(3);
        TreeNode node1 = new TreeNode(1);
        TreeNode node4 = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        node3.left = node1;
        node3.right = node4;
        node4.left = node2;
        recoverTree(node3);
        System.out.println(node3);*/
    }


    /**
     * 遍历一遍，找到了个两个不对的节点，交换
     *
     * @param root
     */
    public static void recoverTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root, pre = null;
        TreeNode first = null, second = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (pre != null && pre.val >= curr.val) {
                // 找到了第一个
                if (first == null) {
                    first = pre;
                    second = curr;
                } else {
                    second = curr;
                    break;
                }
            }
            pre = curr;
            curr = curr.right;
        }
        // 交换两个节点
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}